\documentclass[11pt, letterpaper, twoside]{book}

%\topmargin  0.25in
%\headheight 0.2in
%\headsep    0.3in
%\textheight 8.5in
%\textwidth  6.0in
%\footskip   0.7in

\setlength{\parskip}{1.5ex}

\usepackage[activeacute,spanish]{babel}
\usepackage[dvips]{graphicx}
\usepackage{amsfonts, amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
\pagestyle{plain}

\begin{document}

\frontmatter
\thispagestyle{empty}

\vspace*{2.5cm}
\noindent\makebox{\begin{minipage}{\textwidth}{
\flushright \Huge Asgard \\

}


\noindent\rule{\textwidth}{4pt}

\noindent\flushright { \large Un sistema operativo basado en Sartoris }

\end{minipage}
}

\vspace{8cm}
\noindent\makebox{\begin{minipage}{\textwidth}{
\flushright Santiago Bazerque, Nicol\'as de Galarreta \\
y Mat\'ias Brunstein Macri\\[3.5ex]

para Asgard 1.0, \today.

}
\end{minipage}
}

\newpage
\thispagestyle{empty}
\cleardoublepage

\chapter{Abstract}

Este documento describe el sistema operativo Asgard, basado en el microkernel Sartoris. Asgard es un sistema peque\~no pero con un conjunto de funcionalidades razonablemente completo. Presenta al usuario un shell similar al del venerable sistema Unix (aunque no tan rico), al que se accede via consola (implementando la met\'afora cl\'asica de \emph{consolas virtuales}), que permite al usuario la ejecuci\'on de programas. Cada programa corre en su propio espacio de direcciones paginado aislado del resto del sistema, y la carga en memoria se realiza por el m\'etodo de demand-loading. El sistema utiliza el modo protegido de 32 bits presente en los procesadores x86, y posee un conjunto de drivers de 32 bits que le permiten correr sin precisar del BIOS de la PC (DMA, floppy, disco, VGA en modo texto, teclado, real-time clock y controladora de interrupciones programable o PIC). El sistema sigue tambi\'en la filosof\'ia Unix al presentar al usuario todos estos recursos a trav\'es de un sistema de archivos unificado, llamado OFS, que implementa adem\'as de los conceptos b\'asico \emph{archivo} y \emph{directorio} el de \emph{device file}, dando acceso a varios dispositivos de entrada salida.

\tableofcontents

\mainmatter

\chapter{Introducci\'on}

Asgard es un conjunto de servers que corren sobre Sartoris, un microkernel libre de pol\'\i{}ticas o \emph{puro}. Esto quiere decir que el kernel implementa una capa de abstracci\'on muy delgada, encapsulando solamente al procesador y su unidad de manejo de memoria. De este modo, los conceptos presentados por Sartoris al sistema operativo son tasks, threads, mecanismos b\'asicos para realizar comunicaci\'on inter-task (colas de mensajes y memoria compartida), ligado de threads de ejecuci\'on a interrupciones de hardware y posibilidad de manipular espacios de direcciones paginados. Podr\'\i{}a decirse que el microkernel funciona en este sentido como una librer\'ia, simplificando un conjunto de operaciones que dependen intr\'insecamente de los detalles del hardware subyacente (pero no de \emph{todo} el hardware, sino s\'olo de la CPU, su unidad de manejo de memoria y el mecanismo presente de control de interrupciones). 

Una gran parte de esta funcionalidad se utiliza en solamente uno de los servers que componen el sistema Asgard: el \emph{process manager}. Este server utiliza las abstracciones provistas por Sartoris para crear tasks y threads y para manipular las tablas de p\'aginas del sistema para llevar a cabo la creacion, administraci\'on y destrucci\'on de los procesos de usuario, y realizar el scheduling del procesador, multiplex\'andolo entre estos \'ultimos y los dem\'as servers del sistema.\footnote{Y tambi\'en entre los programas de los usuarios, por supuesto.} A pesar de que este server tiene acceso (a trav\'es del microkernel) a las tablas de p\'aginas del sistema, y en consecuencia a toda la memoria disponible (a excepcion de la memoria utilizada por el microkernel, que se encuentra protegida\footnote{Esta protecci\'on tiene algunas limitaciones en la implementaci\'on acutal de Sartoris.}), se comunica con los dem\'as servers y procesos de usuario utilizando la mensajer\'ia provista por el microkernel. Esto es una constante a trav\'es de los servers que componen Asgard: los servicios provistos se exponen al resto del sistema utilizando protocolos de comunicaci\'on implementados sobre los mecanismos de mensajer\'ia y memoria compartida provistos por Sartoris. La estandarizaci\'on de estos mecanismos de comunicaci\'on permite acceder a todos los recursos del sistema de una forma uniforme: a trav\'es del \emph{OFS server}, que es el server que provee el sistema de archivos principal en Asgard. De esta forma, cuando un programa abre el device file \texttt{/dev/tty0}, el OFS puede utilizar el mecanismo est\'andar para transmitir streams (o sea, comunicarse con lo que se llama \emph{char devices}) para enviar las escrituras y lecturas realizadas sobre este file al servicio encargado de manejar la consola virtual n\'umero cero. El \emph{shell server} utiliza la interfaz de consolas virtuales para proveer al usuario con un entorno similar al de Unix (directorio actual, variables de entorno job control, etc.). El resto de los servers del sistema se encarga de realizar tareas de entrada salida (\emph{fdc}, \emph{hdc} y \emph{stdconsole}) o de proveer soporte a otros servers (\emph{directory}, \emph{dma\_man}, \emph{pipes}). Como referencia futura, la lista completa de servers que componen el sistema Asgard en este momento es la siguiente:

\vspace{0.7cm}

\begin{tabular}{|l|p{0.6\textwidth}|}
\hline
\textbf{process-manager} & Creaci\'on y destrucci\'on de servers y procesos de usuario, scheduling del procesador, paginaci\'on. \\
\hline
\textbf{ofs server} & Sistema de archivos principal, acceso a dispositivos a trav\'es de \emph{device files}. Gran parte del resto del sistema depende de sus servicios. \\
\hline
\textbf{shell server} & Provee un shell a los usuarios del sistema, interact\'ua con el \emph{stdconsle} server y con el \emph{process-manager} (para crear procesos de usuario). \\
\hline
\textbf{directory} & Permite a los distintos servers del sistema ubicarse entre s\'\i{}, independientemente de los \emph{ids} que les haya asignado el \emph{process-manager}. \\
\hline
\textbf{stdconsole} & Implementa un conjunto de consolas virtuales. Contiene drivers para el teclado y el display en modo texto. \\
\hline
\textbf{dma\_man} & Otorga acceso a la controladora de acceso directo a memoria a los dem\'as componentes del sistema, permitiendo que la misma sea compartida entre varios servers. \\
\hline
\textbf{fdc} & Driver de disco flexible. Utiliza el \emph{dma\_man} para acelerar las transferencias usando acceso directo a memoria.\\
\hline
\textbf{hdc} & Driver de disco r\'\i{}gido. Interpreta el esquema de particiones est\'andar.\\
\hline
\textbf{pipes} & Provee \emph{pipes} en el sentido usual de Unix. Es utilizado por el \emph{shell} server para encadenar el output de un programa ejecutado desde la consola al input de otro. \\
\hline
\end{tabular}



\chapter{Sartoris: su interfaz}

Sartoris es un microkernel muy peque\~no. El binario compilado para x86 ocupa en este momento menos de 20 kilobytes \footnote{De hecho, si uno intenta una taxonom\'ia algo m\'as estricta, probablemente Sartoris resulte demasiado peque\~no para ser considerado un microkernel. El t\'ermino \emph{nanokernel} es quiz\'as m\'as adecuado.}. Esto se debe a que Sartoris funciona en buena medida como una librer\'ia que abstrae al conjunto de servers de algunas operaciones de bajo nivel. \footnote{Exceptuando las tareas de inicializaci\'on necesarias para poner en funcionamiento el primer server, que el microkernel debe forzosamente realizar por iniciativa propia (si nos permitimos la antropomorfizaci\'on)}\footnote{Adicionalmente, el microkernel realiza otras tareas quiz\'as m\'as importantes que facilitar ciertas operaciones sobre el hardware: provee mecanismos de comunicaci\'on y protecci\'on.}.

Imaginamos que debe resultar muy f\'acil sobreestimar el rol que Sartoris tiene en el funcionamiento de Asgard. Si bien es el \'unico programa corriendo en modo kernel, todas las llamadas al sistema, veremos, realizan una tarea concreta y f\'acilmente definible. Esto es as\'\i{} hasta tal punto que todas ellas son sin excepci\'on no bloqueantes. De hecho, el microkernel no tiene suficiente control sobre el comportamiento global del sistema como para bloquear un thread. Recordemos que uno de los objetivos del dise\~no de Sartoris es justamente no restringir m\'as all\'a de lo indispensable la forma en la que el sistema operativo pueda comportarse. Sartoris podr\'ia incluso ser utilizado como base para implementar otras aplicaciones que deban correr en modo \emph{stand-alone} sobre el hardware, sin que medie sistema operativo alguno (aunque tal vez haya herramientas mejores para esto, ya que no responde a sus objetivos).\footnote{Seguramente tambi\'en existan herramientas mejores para implementar sistemas operativos. Sin embargo, nosotros preferimos Sartoris.}

Por ejemplo, cuando un server llama al microkernel para pedirle que cree un thread, lo que sucede es que el microkernel crea las estructuras necesarias para poder contener los valores de los registros y algunos datos adicionales (permisos, link al task asociado, otros datos requeridos por el procesador, etc.)  en memoria. En otras palabras, prepara el entorno necesario para poder \emph{ejecutar} ese thread, pero ello no sucede hasta el momento que este u otro server invoquen la llamada de sistema que realiza un cambio de contexto sobre el thread reci\'en creado. Este es el nivel al que en general funcionan las abstracciones presentadas por Sartoris.

\section{Tasks y threads}

Como se vio en el p\'arrafo anterior, el rol de Sartoris en el manejo de tasks y threads es meramente asistencial. Las funciones provistas por el kernel son las siguientes:

\begin{itemize}

\item[] \texttt{create\_task}. Permite crear una nueva tarea. Bajo Sartoris, una tarea es b\'asicamente un espacio de direcciones en el que ejecutan los threads del task. Asismismo, el task es la unidad a partir de la cual funcionan los mecanismos de comunicaci\'on provistos por el microkernel. Los par\'ametros pasados a la funcion permiten indicar el \emph{id} deseado para el nuevo task, su ubicaci\'on en el espacio lineal de memoria y su nivel de privilegio (en general, este \'ultimo variar\'a seg\'un se este creando un server de Asgard o un programa de usuario).
\item[] \texttt{destroy\_task}. Destruye un task creado con la funci\'on anterior a partir de su \emph{id}.
\item[] \texttt{get\_current\_task}. Usada por un proceso (ya sea de usuario o perteneciente a un server) para conocer su \emph{id} de task.
\item[] \texttt{create\_thread}. Esta funci\'on crea un nuevo thread. Los par\'ametros le indican al microkernel el \emph{id} del thread a crear, en el contexto de qu\'e task debe crearse, y los valores iniciales de su \emph{instruction pointer}, flags del procesador y \emph{stack pointer}.
\item[] \texttt{destroy\_thread}. Destruye un thread dado su \emph{id}.
\item[] \texttt{run\_thread} Realiza un cambio de contexto del thread actual a un thread cuyo \emph{id} es pasado como par\'ametro, si se tienen los privilegios necesarios.
\item[] \texttt{get\_current\_thread}. Permite a un thread conocer su \emph{id}.
\item[] \texttt{set\_thread\_run\_mode}. Cambiar el \emph{running mode} del thread. Las opciones implementadas son:
\begin{itemize}
\item[] \texttt{DISABLED} El thread puede ser corrido por nadie.
\item[] \texttt{PRIV\_LEVE\_ONLY} El thread puede ser corrido por todos los threads pertenecientes a tasks cuyo nivel de privilegio sea num\'ericamente menor que un valor suministrado.
\item[] \texttt{PERM\_REQ} Este modo es una extensi\'on del anterior, ya que adem\'as de ser necesario tener como m\'aximo un nivel de prioridad dado debe otorgarse permiso individualmente a cada thread autorizado usando la siguiente funci\'on:
\end{itemize}
\item[] \texttt{set\_thread\_run\_perm}. Otorga autorizaci\'on a un thread para correr a otro.

Estas funciones se utilizan casi exclusivamente en el \emph{process manager} de Asgard, el server encargado de la creaci\'on, destrucci\'on, carga y scheduling de todos los procesos del sistema (ver cap\'\i{}tulo \ref{procesos}).

\end{itemize}

\section{Manejo de memoria}

Las funciones de manejo de memoria de Sartoris pueden dividirse en dos grupos. Las del primero permiten la construcci\'on de espacios de direcciones paginados, y son las siguientes:

\begin{itemize}

\item[] \texttt{page\_in}. Indica al microkernel que se ha introducido una nueva p\'agina al espacio de direcciones de un task (esto podr\'ia deberse a que el programa est\'a siendo tra\'ido de almacenamiento permanente a la memorya o a que se est\'a agregando memoria din\'amicamente a un proceso en ejecuci\'on, por ejemplo). En consecuencia, una nueva entrada es agregada a la tabla de p\'aginas correspondiente por el microkernel.\footnote{Esta funci\'on funciona por niveles, y permite agregar tanto entradas en las tablas de p\'aginas como las propias tablas de p\'aginas.} Esta funci\'on debe ocuparse tambi\'en de actualizar la cache de p\'aginas del procesador (a veces llamada \emph{transaltion lookaside buffer)} de modo de que el cambio sea visible inmediatamente.
\item[] \texttt{page\_out}. Indica al microkernel que se ha retirado una p\'agina (por ejemplo, debido a que debe adjudicarse a otro proceso). Su efecto es que la p\'agina es invalidada en la tabla de p\'aginas, quedando fuera del espacio de direcciones del task correspondiente. Asimismo, el microkernel se encarga de actualizar el cache de p\'aginas del procesador de modo de que el cambio surta efecto de forma instant\'anea.
\item[] \texttt{flush\_tlb}. Limpia la cach\'e de p\'aginas del procesador.
\item[] \texttt{get\_page\_fault}. Devuelve la informaci\'on del \'ultimo fallo de p\'agina ocurrido, de modo de que el server correspondiente pueda resolverlo.

\end{itemize}

Observar nuevamente cu\'an acotada es la acci\'on del microkernel sobre el funcionamiento global del sistema de paginaci\'on (solamente opera sobre las tablas de p\'aginas y la cache del procesador, siguiendo requerimientos de modificaci\'on puntuales). En particular, el algoritmo de paginaci\'on y el transporte de las p\'aginas de memoria pricipal a memoria secundaria y viceversa es realizado por servers corriendo \emph{sobre} el microkernel. Las funciones ofrecidas por Sartoris solamente permiten, una vez que las p\'aginas en cuestion ya est\'an en el lugar deseado de la memoria, habilitarlas permitiendo la modificaci\'on de las tablas de p\'aginas y los caches del procesador usando una interfaz sencilla e independiente, en lo posible, de la arquitectura del procesador sobre el que corre el sistema.

En segundo lugar, el microkernel provee funciones que permiten dar acceso a parte del espacio de direcciones de un task a otros tasks en forma controlada:

\begin{itemize}
\item[] \texttt{share\_mem}. Comparte una regi\'on de memoria contigua del espacio de direcciones del task. Los par\'ametros indican el \emph{id} del task que puede acceder a la memoria compartida y el modo de acceso (lectura, escritura o ambas). Devuelve un nuevo \emph{id} que identifica un\'\i{}vocamente la regi\'on compartida en el sistema.\footnote{En la terminolog\'ia de Sartoris, este \emph{id} identifica un \emph{shared memory object} o \emph{SMO}.}
\item[] \texttt{claim\_mem}. Reclama la regi\'on de memoria identificada por el \emph{id} dado (que debe pertenecer al task que realiza la llamada) de modo de que deje de ser accesible por el task con el que hab\'ia sido compartida.
\item[] \texttt{read\_mem}. Copia toda o parte de una regi\'on de memoria compartida del espacio de direcciones del task al que pertenece la regi\'on al espacio de direcciones del task que realiza la llamada (que debe ser el destinatario de la regi\'on y tener permiso de lectura). Los par\'ametros indican qu\'e bytes copiar y un buffer en el espacio de direcciones del task actual a utilizar como destino.
\item[] \texttt{write\_mem}. El comportamiento es an\'alogo al de la funci\'on anterior, pero en este caso un buffer en el espacio de direcciones del task que realiza la llamada es copiado al espacio de direcciones de otro task que previamente hubiese otorgado acceso a su espacio de direcciones al primero.
\item[] \texttt{pass\_mem}. El objeto de esta funci\'on es evitar copias innecesarias entre buffers cuando ello pueda evitarse. Permite a un task dar acceso a otros tasks a aquellas regiones de memoria a las que a su vez \'el mismo ha recibido acceso.\footnote{Para intentar evitar que esta funcionalidad complique demasiado los escenarios de protecci\'on de memoria a considerar, la region en cuestion deja de ser accesible por el task que realiza la llamada, quedando esta disponible s\'olo en el contexto del task cuyo \emph{id} es pasado a la funci\'on \texttt{pass\_mem}.}
\item[] \texttt{mem\_size}. Permite conocer el tama\~no de una regi\'on compartida.
\end{itemize}

Esta interfaz es utilizada en Asgard para realizar la transferencia de datos de los servers que realizan entrada/salida hacia el resto del sistema. Por ejemplo, cuando el server \emph{fdc} lee un bloque del disco flexible, el \emph{ofsservice} accede a los bytes le\'idos a trav\'es de una regi\'on de memoria compartida entre ambos tasks. A su vez, equellos tasks que hagan uso del sistema de archivos depender\'an de regiones compartidas en su espacio de direcciones para poder dar acceso al \emph{ofsservice} a los buffers internos que permiten la transferencia de datos.


\section{Colas de mensajes}

Si bien las regiones de memoria compartida que fueron descriptas en la secci\'on anterior permiten acceder a informaci\'on de un task desde otro, en s\'\i{} mismas no resultan suficientes para permitir la interacci\'on deseada entre tasks. Esto se debe a que falta un mecanismo para transmitir los \emph{id} de las regiones creadas de un task a otro. El mecanismo provisto por Sartoris para comenzar y controlar este tipo de comunicaciones consiste en otorgar a cada task un conjunto de puertos que funcionan como colas de mensajes o casillas de correo en las que otros tasks pueden dejar mensajes de tama\~no fijo (16 bytes, en este momento). Como veremos, el env\'io de mensajes es asincr\'onico. La interfaz de acceso a las colas de mensajes provistas por el kernel es la siguiente:

\begin{itemize}

\item[] \texttt{open\_port}. Abre un puerto del task actual, habilitando la recepci\'on de mensajes. Los modos de apertura son an\'alogos a los disponibles para controlar la invocaci\'on de threads: puede limitarse el acceso seg\'un el nivel de privilegio del task que intenta enviar el mensaje, y opcionalmente puede otorgarse acceso solo a algunos tasks individualmente.
\item[] \texttt{close\_port}. Cierra un puerto del task actual previamente abierto, descartando los mensajes que pudieran estar esperando rececpci\'on.
\item[] \texttt{set\_port\_mode}. Permite cambiar el modo de restricci\'on de env\'\i{}o en un puerto que ya se encuentra abierto.
\item[] \texttt{set\_port\_perm}. Otorga acceso a un task a un port abierto dado.
\item[] \texttt{send\_msg}. Env\'ia un mensaje (16 bytes de datos) a otro port. Esta funci\'on, al igual que todas las dem\'as llamadas al sistema, retorna en forma inmediata. El mensaje queda almacenado en la cola de mensajes del task receptor, quedando disponible para ser recibido a trav\'es de la funci\'on \texttt{get\_msg}.
\item[] \texttt{get\_msg}. Recibe el primer mensaje en la cola correspondiente a un puerto dado, siempre y cuando la mimsa no se encontrase en ese momento vac\'\i{}a.
\item[] \texttt{get\_msg\_count}. Indica la cantidad de mensajes esperando en un puerto del task actual.

\end{itemize}

Siguiendo con el ejemplo de la secci\'on anterior, cuando el filesystem server (el \emph{ofsserver} en Asgard) precisa que el \emph{fdc} server lea un sector del floppy, env\'\i{}a un mensaje a un puerto espec\'\i{}fico del \emph{fdc} cuyo contenido especifica qu\'e sector debe leerse, y probablemente el puerto en el que el \emph{ofsserver} espera un mensaje de respuesta indicando el resultado de la operaci\'on.\footnote{En un intento por estandarizar este tipo de comunicaciones, creamos un conjunto de protocolos. Los mismos se describen en el cap\'\i{}tulo \ref{protocolos}.}

\section{Interrupciones}

Por \'ultimo, las siguientes funciones de Sartoris premiten vincular un thread a una excepci\'on del procesador o una interrupci\'on de hardware:

\begin{itemize}

\item[] \texttt{create\_int\_handler}. Asocia una interrupci\'on o excepci\'on (a partir del valor num\'erico de su posici\'on en el vector de interrupciones tal como el mismo fue definido por Sartoris) a un thread. Esto provoca que cada vez que la interrupci\'on ocurre, el microkernel realiza un cambio de tarea al thread indicado en forma autom\'atica.
\item[] \texttt{destroy\_int\_handler}. Destruye la asociaci\'on creada por la funci\'on anterior, ocurrencias posteriores de la interrupci\'on dejan de provocar cambios de tarea al thread que hab\'\i{}a sido sumnistrado como \emph{handler}.
\item[] \texttt{ret\_from\_int}. Esta funci\'on s\'olo deber\'ia llamarse en el contexto de un \emph{interrupt handler}, y provoca un cambio de contexto de vuelta al thread que estaba corriendo antes de que se disparase la interrupci\'on
\item[] \texttt{get\_last\_int}. Provee informaci\'on sobre la \'ultima interrupci\'on disparada. Permite la implementaci\'on de \emph{handlers} que se ocupen de varias interrupciones diferentes.

\end{itemize}

En la pr\'actia, los threads asociados a interrupciones raramente son invocados en forma directa utilizando la funci\'on \texttt{run\_thread}. Comunmente, los servers que realizan entrada/salida via interrupciones funcionan en alguna variante del modelo productor-consumidor, con uno o m\'as threads asociados a interrupciones manejando la interacci\'on directa con el dispositivo, y otro conjunto de threads disjunto del primero que recibe los pedidos (a trav\'es del mecanismo de mensajer\'ia provisto por el microkernel), inicia las operaciones de entrada/salida necesarias, y luego procesa los resultados y env\'\i{}a el status de la operaci\'on a los usuarios del server.


\chapter{Manejo de procesos en Asgard} \label{procesos}

El \emph{process-manager} es el server a cargo del manejo de procesos en Asgard. Al final de la secuencia de booteo, es cargado a memoria por el microkernel desde una ubicaci\'on prefijada en el medio de booteo. Una vez en ejecuci\'on, se encarga de ubicar al resto de los servers del sistema en memoria y crear todos los tasks y threads necesarios para su funcionamiento. Consta de dos threads: el primero est\'a asociado a la interrupci\'on del timer, y por lo tanto es invocado a intervalos regulares. Este thread realiza algunas operaciones de \emph{housekeeping}, como por ejemplo recibir los pedidos de craci\'on y destrucci\'on de procesos en un puerto de mensajer\'ia determinado, y luego realiza su tarea principal, que es decidir cu\'al es el proceso (ya sea de usuario o server) que debe correr a continuaci\'on y solocitar el cambio de contexto correspondiente al kernel. El segundo thread est\'a asociado a todas las excepciones definidas por el procesador. De este modo, detecta todos los errores y situaciones excepcionales encontrados por los procesos, incluyendo los fallos de p\'agina. Cuando se produce uno de estos \'ultimos, solicita las lecturas a disco que sean necesarias para satisfacerlo (si hubiese alguna). Las respuestas a estos pedidos son procesadas posteriormente por el thread principal, que se encarga de volver a activar los threads en estado de bloqueado por fallo de p\'agina una vez que el fallo haya sido resuelto. 

\section{Inicializaci\'on}

En un primero momento, el \emph{process-manager} es cargado a memoria en una direcci\'on arbitraria, definida por el microkernel.\footnote{Actualmente al comienzo del octavo megabyte de memoria.} El proceso de inicializaci\'on consiste en:

\begin{itemize}
\item Crear el process manager definitivo, cuyo \emph{task id} es 0, ubic\'andolo en un chunk contiguo de memoria inmediatamente a continuaci\'on del final de la memoria reservada por la placa de video.
\item Realizar un cambio de cotexto a la instancia del \emph{process-manager} reci\'en creada.
\item Corriendo ya como el \emph{process-manager} definitivo, destruir la instancia creada por el kernel.
\item Organizar toda la memoria disponible en el sistema en una lista encadenada de p\'aginas libres.
\item Inicializar las estructuras de datos internas al \emph{process-manager}.
\item Crear todos los servers que componen el sistema Asgard a partir de la imagnen que el \emph{process-manager} tiene de cada uno de ellos en su espacio de direcciones, tomando la memoria necesaria de la lista anteriormente creada. La memoria restante queda disponible en la lista para los procesos de usuario (en una maquina moderna, la abrumadora mayor\'\i{}a).
\item Asociar el thread principal del process manager a la interrupci\'on del \emph{timer}, de modo de que corra peri\'odicamente.
\item Crear el thread secundario y asociarlo a las excepciones del procesador correspondientes. 
\end{itemize}

En este punto el \emph{process-manager} est\'a listo para comenzar a operar normalmente.

\section{Procesos}

La creaci\'on y destrucci\'on de tasks y threads es controlada a trav\'es de un puerto de control, en el que el \emph{process-manager} recibe mensajes (usualmente del \emph{shell} server) indicando qu\'e archivo se desea ejecutar. Una vez recibido uno de estos mensajes, comienza un proceso de \emph{randez-vous} con el \emph{ofs} server, al final del cual el \emph{process-manager} obtiene un \emph{file descriptor} o identificador de archivo que le permite acceder a su contenido, y adicionalmente conoce algunos datos adicionales para poder paginar correctamente (como el tama\~no del archivo). Notar que inicialmente, al crear un task, no se trae a memoria el contenido del archivo asociado. El \emph{file descriptor} obtenido ser\'a usado durante la ejecuci\'on del programa para traer las p\'aginas de c\'odigo de su espacio de direcciones que sean usadas. Este proceso se conoce como \emph{demand loading} o carga por demanda.

\section{Scheduling}

El scheduling del procesador es realizado por el thread principal, que elige qu\'e proceso ejecutar a continuaci\'on de procesar todos los requierimientos y confirmaciones recibidos a trav\'es de la mensajer\'ia del microkernel. Despu\'es de realizado el cambio de contexto al proceso correspondiente, el mismo se ejecuta durante un cuanto de procesador (por defecto, 5 milisegundos). Una vez finalizado este per\'iodo, la interrupci\'on del \emph{timer} se dispara nuevamente y el scheduler vuelve a tomar control del procesador. Por el momento, el algoritmo utilizado para correr tanto los procesos de usuario como los servers es el denominado \emph{round-robin}. Los procesos solamente se bloquean a nivel del \emph{process-manager} cuando tienen un fallo de p\'agina, y no son ejecutados hasta que la misma sea tra\'ida del disco. Por el momento, no es posible bloquear un thread a nivel de \emph{process-manager} por otros motivos (por ejemplo, esperar la realizaci\'on de una operaci\'on de entrada salida). Lo que sucede en la pr\'actica es que un thread que est\'a esperando datos de un server y es ejecutado por el process manager antes de que los mismos hayan llegado, sencillamente compureba que no tiene mensajes en el puerto en el que espera la llegada de sus datos y vuelve a poner el procesador en manos del \emph{process-manager} por medio de una llamada a \texttt{run\_thread}. Si bien este mecanismo funciona sin problemas, no es \'optimo con respecto a la cantidad de cambios de contexto realizados. La interfaz del \emph{process-manager} define mecanismos para que un proceso no sea corrido hasta que un server determinado as\'i lo indique, pero est\'a funcionalidad no ha sido implementada todav\'\i{}a.

\section{Paginaci\'on}

Asgard utiliza paginaci\'on para permitir que el tama\~no de los procesos cambie durante su ejecuci\'on, y para evitar tener que lidiar con la fragmentaci\'on de la memoria. No soporta en su versi\'on actual enviar p\'aginas a memoria secundaria en caso de que la principal se agote, por el sencillo motivo de que eso, por el momento, nunca sucede. Luego se ha preferido mejorar el sistema en otros aspectos. Sin embargo, el sistema posee un sistema din\'amico de manejo de la memoria que funciona en forma estable. Los \'unicos fallos de p\'agina que involucran lecturas de disco son los provocados por el \emph{demand loading}, que provocan que se dispare el mecanismo de bloqueo mencionado en la secci\'on anterior. Una particularidad del esquema elegido para el manejo de memoria es que funciona pr\'acticamente sin metadatos. La lista de p\'aginas libres est\'a implementada sobre las mismas p\'aginas libres que contiene, y cuando es necesario recuperar la memoria utilizada por un proceso que est\'a siendo destruido sus tablas de p\'aginas son recorridas devolviendo la memoria que contienen (y las tablas de p\'aginas mismas) a la lista de memoria libre. Si bien este mecanismo no es extremadamente eficiente, tiene la ventaja de ser hermosamente sencillo y en la pr\'actica funciona bien. Al menos en los escenarios acotados en los que hemos podido probar el sistema, su impacto es nulo sobre el funcionamiento global del mismo. 

A continuaci\'on se detallan los pasos a seguir para satisfacer un fallo de p\'agina en Asgard. Las siguientes acciones son tomadas directamente por el \emph{handler} del fallo, en forma inmediata:

\begin{itemize}
\item Verificar que la direcci\'on que provoc\'o el fallo pertenezca al espacio de direcciones del proceso en cuyo contexto ocurri\'o.
\item En caso de que la tabla de p\'aginas en la que se debe insertar la nueva p\'agina todav\'\i{}a no haya sido agregada al espacio de direcciones del proceso, tomar una p\'agina de la lista de memoria libre e insertarla como la tabla de p\'aginas faltante.
\item En caso de que el fallo de no corresponda al c\'odigo del programa (o sea, se debe a un aumento din\'amico en la necesidad de memoria del proceso, por ejemplo debido al uso de \texttt{malloc} y \texttt{free}), tomar una p\'agina de la lista de memoria libre, insertarla en la tabla correspondiente e iniciar un cambio de contexto de vuelta al thread que provoc\'o el fallo.
\item En caso de que el fallo corresponda al c\'odigo o datos inicializados del progrma, inicar la lectura del sector correspondiente enviando un mensaje de \emph{seek} para el \emph{file descriptor} asociado al task al sistema de archivos. Cambiar el estado del thread que provoc\'o el fallo a bloqueado, e iniciar un cambio de contexto al \emph{scheduler} (el otro thread del \emph{process-manager}) para que elija a un nuevo thread a ejecutar.

\end{itemize}

El resto del mecanismo de manejo de fallos de p\'agina sucede en el thread principal, que rutinariamente recibe las confirmaciones enviadas por el filesystem a los mensajes de \emph{seek} enviados desde el \emph{handler} de fallos de p\'agina, y solicita a continuaci\'on la operaci\'on de lectura, dado que el \emph{file pointer} ya se encuentra en el lugar indicado. Una vez finalizada la lectura, la p\'agina que acaba de ser tra\'\i{}da a memoria es insertada en el espacio de direcciones del thread cuyo bloqueo provoc\'o, quedando el mismo listo para ser ejecutado una vez m\'as.

\chapter{El sistema de archivos OFS}

El \emph{Obsession File System} es el sistema de archivos principal de Asgard. Los objetivos que fueron tenidos en cuenta su dise\~no son la \emph{confiabilidad}, la \emph{simplicidad} y la \emph{extensibilidad}. Para permitir el acceso a otros sistemas de archivos a trav\'es del \emph{OFS}, presentando una visi\'on unificada del almacenamiento, se estandariz\'o la interfaz exportada por los servers que implementan sistemas de archivos. Tambi\'en se estandariz\'o la interfaz de los servers que act\'uan como drivers de dispositivos de almacenamiento, display, etc. Esto permite al \emph{OFS}, en primer lugar, acceder al medio en el que residen sus archivos en forma independiente del mismo (siempre y cuando el server que implementa el acceso al hardware utilice la interfaz est\'andar), y en segundo dar acceso a toda una variedad de dispositivos a trav\'es de \emph{device files}.

\section{Interfaz}

La interfaz presentada por el \emph{OFS}, y que debe ser implementada tambi\'en por aquellos servers de sistemas de archivos que deban ser montados sobre el filesystem principal, contiene los siguientes mensajes:

\begin{itemize}

\item[] \textbf{Control}. El mensaje \texttt{INIT} es enviado al server al comienzo de su ejecuio\'on. Su objeto es permitir la carga de drivers y filesystem servers a memoria bajo demanda. Por otro lado, los mensajes \texttt{MOUNT} y \texttt{UMOUNT} permiten acceder a particiones o dispositivos espec\'ificos.
\item[] \textbf{Manejo de archivos}. Los mensajes \texttt{OPEN}, \texttt{CLOSE}, \texttt{READ}, \texttt{WRITE}, \texttt{PUTC}, \texttt{PUTS}, \texttt{GETC}, \texttt{GETS}, \texttt{SEEK}, \texttt{TELL} y \texttt{FLUSH} conforman la interfaz est\'andar de acceso a archivos.
\item[] \textbf{Comandos estructurales}. Los mensajes \texttt{LINK}, \texttt{MKDIR}, \texttt{MKDEVICE}, \texttt{CHANGEATT} y \texttt{DELETE} manipulan la estructura jer\'arquica del sistema de archivos y permiten configurar el acceso a dispositivos.
\item[] \textbf{Inspecci\'on}. Los comandos \texttt{FILEINFO} y \texttt{EXISTS} son usados para obtener informaci\'on sobre archivos.
\item[] \textbf{Comandos adicionales}. El mensaje \texttt{IOCTL} permite enviar comandos dependientes del dispositvo al que se quiera acceder en forma unificada, y el comando \texttt{FORWARD} se usa en la implementaci\'on de sub-filesystems en conjunci\'on con los comandos \texttt{MOUNT} y \texttt{UMOUNT}.

\end{itemize}

\section{Disk layout}

La organizaci\'on en disco del \emph{OFS} es la siguiente:

\begin{center}
\begin{tabular}{c|c|c|c|c}
OFST & [METADATOS] & GRUPO$_1$ & ... & GRUPO$_n$
\end{tabular}
\end{center}

La \emph{OFST} es una esctructura que contiene informaci\'on sobre la partici\'on, como por ejemplo la cantidad de veces que ha sido montada, el tama\~no de bloque de datos, el offset del primer grupo de datos en la partici\'on, etc. Cada grupo es un conjunto de sectores contiguos en el disco, y contiene nodos que permiten interpretar los datos contenidos en el grupo y bloques en los que residen los datos propiamente dichos. Los grupos fuero introducidos por dos motivos:
\begin{itemize}
\item Incrementan la localidad de los datos en el disco.
\item Distribuyen los metadatos (que se encuentran en los nodos) a lo largo de todo el disco, disminuyendo las chances de que algunos pocos sectores defectuosos del disco impidan acceder a grandes cantidades de informaci\'on.
\end{itemize}
La estructura de un grupo es la siguiente:
\begin{center}
\begin{tabular}{c|c|c|c|c}
GH & BITMAP NODOS & BITMAP BLOQ. & TABLA NODOS & TABLA BLOQ.
\end{tabular}
\end{center}
No obstante la organizaci\'on en grupos, los bloques que contengan los datos de un archivo podr\'\i{}an estar repartidos por todo el disco (el sistema de archivos lo sporta). Sin embargo, por las razones mencionadas arriba, esto no es recomendable.

\section{OFS Service}

El server del \emph{OFS} posee un thread principal, que recibe los mensajes solicitando operaciones y las confirmaciones de los servers que acceden a dispositivos u otros filesystems, y un pool de threads de trabajo que llevan a cabo los comandos recibidos. Es tarea del thread principal encolar los comandos pendientes, decidir qu\'e comandos pueden ser ejecutados evitando el uso concurrente de recursos cr\'iticos que pueda conducir a deadlocks o subvertir la sem\'antica secuencial de las operaciones, y finalmetne asignar threads de trabajo a cada comando particular que va a correrse.

Un recurso cr\'\i{}tico fundamental en la implementaci\'on del \emph{OFS} son los nodos que contienen los metadatos del sistema de archivos, o sea la estructura de bloques que contiene a cada archivo y a cada directorio. Por este motivo, el acceso a los nodos utiliza un esquema de protecci\'on por sem\'aforos para evitar que varios threads de trabajo accedan en forma concurrente a un nodo. Algunas operaciones tambi\'en requieren acceso exclusivo a dispositivos para ser llevadas a cabo con seguridad.

El sistema de archivos utiliza caches en dos niveles diferentes. Los datos de los \emph{devices} que han sido utilizados recientemente son guardados en un \'arbol AVL, intentando acelerar futuros accesos. Cuando el \'arbol se torna demasiado grande, un algoritmo basado en la cantidad de hits recientes es utilizado para decidir qu\'e dispositivo descartar. Por otro lado, los buffers usados para transferencia de datos recientes tambi\'en son almacenados, en un intento por explotar la localidad en el acceso a archivos. Cuando a su vez la cantidad de buffers resulta excesiva, se utiliza un algoritmo basado en un sistema de cr\'editos para decidir cu\'al debe ser descartado. Los cr\'editos de un buffer $b$ se definen como
\begin{displaymath}
C(b)=\left\{
\begin{array}
[c]{ll}%
b.hits\ast b.grace\_period\ast length(b.opened\_files)& \text{for }b.hits\text{ }\leq\text{ }max\_hits\\
0 & \text{for }b.hits\text{ }>\text{\ }max\_hits
\end{array}
\right.
\end{displaymath}
donde $b.hits$ representa la cantidad de veces que el buffer fue accedido, $b.grace\_period$ se decrementa cada vez que debe removerse un bloque, con lo que resulta un estimador de la \emph{edad} del buffer y $b.opened\_files$ es la lista de archivos abiertos que est\'an utilizando el buffer. El buffer cuyos cr\'editos resultan menores es removido.


\begin{thebibliography}{99}
\bibitem{Sar} Santiago Bazerque, Nicol\'as de Galarreta: \emph{Introduction to the Sartoris Microkernel Architecture, design concepts ans implementation notes for the x86 platform}, disponible en \texttt{sartoris.sourceforge.net}.
\bibitem{OFS} Nicol\'as de Galarreta, Santiago Bazerque: \emph{Obseesion File System, design concepts and implementation of the service}, disponible en \texttt{sartoris.sourceforge.net}.
\end{thebibliography}

\end{document}
